#include <bits/stdc++.h>

using namespace std;

struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution
{
public:
    // bool recursion(TreeNode *root, int targetSum, int sum)
    // {
    //     if (root->left == nullptr && root->right == nullptr)
    //     {
    //         if (sum == targetSum)
    //         {
    //             return true;
    //         }
    //         else
    //         {
    //             return false;
    //         }
    //     }
    //     bool flag1 = false;
    //     if (root->left)
    //     {
    //         flag1 = recursion(root->left, targetSum, sum + root->left->val);
    //     }
    //     bool flag2 = false;
    //     if (root->right)
    //     {
    //         flag2 = recursion(root->right, targetSum, sum + root->right->val);
    //     }
    //     return flag1 || flag2;
    // }

    // bool hasPathSum(TreeNode *root, int targetSum)
    // {
    //     if (root == nullptr)
    //     {
    //         return false;
    //     }
    //     return recursion(root, targetSum, root->val);
    // }

    // bool recursion(TreeNode* root,int count)
    // {
    //     if(root->left==nullptr&&root->right==nullptr&&count==0)
    //     {
    //         return true;
    //     }
    //     if(root->left==nullptr&&root->right==nullptr)
    //     {
    //         return false;
    //     }
    //     if(root->left)
    //     {
    //         if(recursion(root->left,count-root->left->val))
    //         {
    //             return true;
    //         }
    //     }
    //     if(root->right)
    //     {
    //         if(recursion(root->right,count-root->right->val))
    //         {
    //             return true;
    //         }
    //     }
    //     return false;
    // }

    // bool hasPathSum(TreeNode *root, int targetSum)
    // {
    //     if(root==nullptr)
    //     {
    //         return false;
    //     }
    //     return recursion(root,targetSum-root->val);
    // }

    bool hasPathSum(TreeNode *root, int targetSum)
    {
        if(root==nullptr)
        {
            return false;
        }
        stack<pair<TreeNode*,int>> stk;
        stk.push(make_pair(root,root->val));
        while(!stk.empty())
        {
            pair<TreeNode*,int> cur=stk.top();
            stk.pop();
            if(cur.first->left==nullptr&&cur.first->right==nullptr&&cur.second==targetSum)
            {
                return true;
            }
            if(cur.first->right)
            {
                stk.push(make_pair(cur.first->right,cur.second+cur.first->right->val));
            }
            if(cur.first->left)
            {
                stk.push(make_pair(cur.first->left,cur.second+cur.first->left->val));
            }
        }
        return false;
    }
};

int main()
{
    TreeNode *root = new TreeNode(5);
    root->left = new TreeNode(4);
    root->right = new TreeNode(8);
    root->left->left = new TreeNode(11);
    root->left->left->left = new TreeNode(7);
    root->left->left->right = new TreeNode(2);
    root->right->left = new TreeNode(13);
    root->right->right = new TreeNode(4);
    root->right->right->right = new TreeNode(1);
    Solution sol;
    cout << sol.hasPathSum(root, 22) << endl;
    return 0;
}